package com.mj.listen1._12_堆.heap;

import java.util.Comparator;

/**
 * 小顶堆
 */
public class MinBinaryHeap<E> extends AbstractHeap<E> {

    private static final int DEFAULT_CAPACITY = 10;

    private E[] elements;

    public MinBinaryHeap(E[] elements, Comparator<E> comparator) {
        super(comparator);
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(DEFAULT_CAPACITY, elements.length);
            this.elements = (E[]) new Object[capacity];
            // 将传入的数组中的元素添加到堆内部数组中
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            // 批量建堆的方法
            heapify();
        }
    }

    public MinBinaryHeap(E[] elements) {
        this(elements, null);
    }

    public MinBinaryHeap(Comparator<E> comparator) {
        this(null, comparator);
    }

    public MinBinaryHeap() {
        this(null, null);
    }

    @Override
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        // 扩容
        if (size == elements.length) {
            resize((elements.length >> 1) + elements.length);
        }
        elements[size++] = element;
        siftUp(size - 1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();

        E root = elements[0];
        // 将数组最后的节点,替代堆顶节点; 这样做的目的是为了减少移动,提高效率
        elements[0] = elements[size - 1];
        elements[size - 1] = null;// 删除最后一个节点

        size--;

        // 最后一个元素放到数组索引0的位置后, 要进行下滤, 修复二叉堆性质
        siftDown(0);

        return root;// 返回的是删除的堆顶元素
    }

    @Override
    public E replace(E element) {
        elementNotNullCheck(element);
        E root = null;
        if (size == 0) {
            // 没有任何元素，则添加元素。把替换元素放置到堆顶
            elements[0] = element;
            size = 1;
        } else {
            // 记录堆顶元素
            root = elements[0];
            // 替换堆顶元素
            elements[0] = element;
            // 从最新堆顶进行下滤
            siftDown(0);
        }
        return root;
    }


    private void heapify() {
        // 方法一：自上而下上滤
//        for (int i = 0; i < size; i++) {
//            siftUp(i);
//        }

        // 方法二：自下而上下滤
        // 开始的索引是 (size >> 1) - 1 ，这个索引位置的 。size >> 1 个非叶子节点
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 把index位置的节点上滤
     *
     * @param index
     */
    private void siftUp(int index) {
//        E element = elements[index];
//        while (index > 0) {
//            // 父亲节点对应物理数组中的索引
//            int parentIndex = (index - 1) >> 1;
//            // 父亲节点值
//            E parent = elements[parentIndex];
//            // 比较自己和父亲哪个大
//            if (compare(element, parent) <= 0) return;// 自己比父亲要小
//
//            // 走这里说明父亲比自己小
//
//            // 说明孩子节点大于父亲节点，需要交换位置上的值
//            E temp = elements[parentIndex];
//            elements[parentIndex] = element;
//            elements[index] = temp;
//
//            // index指针指向父亲，此时父亲作为孩子，再去拿着这个index为的数据去根新的父亲做比较
//            index = parentIndex;
//        }


        // 优化
        E element = elements[index];
        while (index > 0) {
            // 父亲节点对应物理数组中的索引
            int parentIndex = (index - 1) >> 1;
            // 父亲节点值
            E parent = elements[parentIndex];
            // 比较自己和父亲哪个大
            if (compare(element, parent) >= 0) break;// 自己比父亲要大

            // 直接让父节点位置的值覆盖index位置的值
            elements[index] = parent;

            // index指针指向父亲，此时父亲作为孩子，再去拿着这个index为的数据去根新的父亲做比较
            index = parentIndex;
        }
        elements[index] = element;
    }

    /**
     * 让index位置的元素进行下滤操作, 最后一个元素放到数组索引0的位置后,可能不满足二叉堆的性质,要进行下滤, 修复二叉堆性质
     *
     * @param index 需要进行下滤的节点, 肯定是非叶子节点,因为要和他的子节点比较, 得到堆顶元素
     */
    private void siftDown(int index) {
        // 拿这个值往下比较
        E element = elements[index];
        // 非叶子节点的数量: 公式:floor (n / 2)。最后一个非叶子节点的索引：index = size >> 1 - 1; 第一个叶子节点的索引 size >> 1
        int notLeafCount = size >> 1;
        /*
            完全二叉树, 从上至下,从左向右,遇到的第一个叶子节点, 它后面的节点必然是叶子节点, 完全二叉树性质
            也就是说, 当index小于第一个叶子节点的索引, 那么index肯定不是叶子节点

            第一个叶子节点的索引 = 非叶子节点的数量 = size / 2
        */

        // 确保index位置的元素必须要有子节点, 然后和最大的子节点进行交换位置
        // 如果index位置的元素 大于 它的子节点, 则不需要交换, 符合二叉堆性质, 退出循环

        /*
            第一个叶子节点的索引 = 非叶子节点的数量
            index < 第一个非叶子节点的数量, 就表示它肯定是有子节点的
        */

        // 循环停止条件：当前index索引必须还有子节点
        while (index < notLeafCount) {
            // 默认比较的是左子节点
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];

            // 找出右子节点
            int rightIndex = childIndex + 1;
            // rightIndex < size说明存在右子节点，否则的话不存在右子节点
            // compare(elements[rightIndex], child) < 0说明右子节点小
            if (rightIndex < size && compare(elements[rightIndex], child) < 0) {
                // 右子节点小，更换为右子节点
                childIndex = rightIndex;
                child = elements[rightIndex];
            }

            // 与子节点比较。发现元素比所有的叶子节点值要小
            if (compare(element, child) <= 0) break;// 停止查找

            // 替换
            // 将子节点存放到index位置; `然后要将childIndex赋值给index`, 也就是说此时的堆顶节点跑到了childIndex的位置,
            // 所以要将更换堆顶节点index的值, 就需要使用 index = childIndex; 因为下一轮还是需要index的堆顶元素再和它的子节点比较, 以此类推
            elements[index] = child;
            // 更新index指针，指向子节点位置
            index = childIndex;
        }
        // 找到后最后的替换
        elements[index] = element;
    }

    // 元素不为空检查
    private void elementNotNullCheck(E element) {
        if (null == element) {
            throw new IllegalArgumentException("element not null");
        }
    }

    /**
     * 数组扩容
     * 扩容原来大小的1.5倍。(elements.length >> 1)：除以2
     * resize((elements.length >> 1) + elements.length);
     */
    private void resize(int newCapacity) {
        E[] newElements = (E[]) new Object[newCapacity];
        // 把原数组元素放置到新数组
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        System.out.println(elements.length + "扩容到：" + newCapacity);
        // 指针指向新的数组
        elements = newElements;
    }

    @Override
    public Object root() {
        return 0;
    }

    @Override
    public Object left(Object node) {
        int index = ((int) node << 1) + 1;
        return index >= size ? null : index;
    }

    @Override
    public Object right(Object node) {
        int index = ((int) node << 1) + 2;
        return index >= size ? null : index;
    }

    @Override
    public Object string(Object node) {
        Integer index = (Integer) node;
        return elements[index];
    }
}
